/**
 * 判读字符是否是运算符
 * @param {string} char 字符
 * @returns {Boolean}
 */
function isOperator (char) {
  let operatorString = '+-*/()'
  return operatorString.indexOf(char) > -1
}

/**
 * 获取优先级
 * 加减为1，乘除为2，其他为0。
*/
function getPrioraty (value) {
  switch (value) {
    case '+':
    case '-':
      return 1
    case '*':
    case '/':
      return 2
    case '(':
      return 3
    default:
      return 0
  }
}

/**
 * 比较运算符优先级
*/
function prioraty (o1, o2) {
  return getPrioraty(o1) >= getPrioraty(o2)
}

/**
 * @constant {Object} STATUS 状态
 * STATUS.BEGINNING 起始状态
 * STATUS.OPERATOR 运算符
 * STATUS.FACTOR 公式因子
 * STATUS.VALUE 值 只在计算时使用
*/
const STATUS = {
  BEGINNING: 'BEGINNING',
  OPERATOR: 'OPERATOR',
  FACTOR: 'FACTOR',
  VALUE: 'VALUE'
}

/**
 * 解析公式表达式
 * @param {string} formulaStr 公式表达式
 * @returns {Array} result 解析结果
 */
function parseFormulaStr (formulaStr) {
  // 过滤掉空白字符
  formulaStr = formulaStr.replace(/\s/g, '')

  let result = []
  let state = STATUS.BEGINNING
  let index = 0
  let subString = ''
  let char = ''

  // 推出当前状态
  function exit () {
    result.push({
      state: state,
      subString: subString
    })
    state = STATUS.BEGINNING
    subString = ''
  }

  // 进入新的状态
  function newState (newState) {
    subString += char
    state = newState
    index++
  }

  while (index < formulaStr.length) {
    char = formulaStr[index]

    switch (state) {
      case STATUS.BEGINNING:
        if (isOperator(char)) {
          newState(STATUS.OPERATOR)
        } else {
          newState(STATUS.FACTOR)
        }
        break
      case STATUS.OPERATOR:
        exit()
        break
      case STATUS.FACTOR:
        if (isOperator(char)) {
          exit()
        } else {
          newState(STATUS.FACTOR)
        }
        break
      default:
        break
    }
  }

  if (state !== STATUS.BEGINNING) {
    exit()
  }

  return result
}

/**
 * 生成逆波兰式
 * @param {Array} parseResult 公式表达式的解析结果 来自 parseFormulaStr
 * @returns {Array} outputStack 逆波兰式（后缀表达式）
 */
function dal2Rpn (parseResult) {
  /**
  * 代码流程：
  * 参考：《数据结构与算法分析》第三版 3.6.3
  */
  let inputArray = parseResult.map(d => d) // 避免直接操作parseResult
  // 操作符栈
  let operatorStack = []
  // 输出
  let outputStack = []
  // 当前的待处理项
  let cur

  let index = 0
  function show1 (params) {
    console.log('-----', parseResult.map(d => '-').join(' '), '-----')
    console.log('输入栈:', parseResult.map(d => d.subString).join(' '))
    console.log('栈光标:', parseResult.map( (d,i) => {
      if (i === index) {
        return d.subString
      } else {
        var sub = ''
        for (var i = 0; i < d.subString.length; i++) {
          sub += ' '
        }
        return sub
      }
    }).join(' '))
    index++
  }

  function show2 () {
    console.log('符号栈:', operatorStack.map(d => d.subString).join(' '))
    console.log('输出栈:', outputStack.map(d => d.subString).join(' '))
    console.log('-----', parseResult.map(d => '-').join(' '), '-----')
    console.log('')
  }

  while (inputArray.length > 0) {
    show1()
    
    cur = inputArray.shift()

    if (isOperator(cur.subString)) {
      if (cur.subString === ')') {
        /* 
          匹配到右括号：operatorStack(操作符栈) 中 运算符 依次移入 outputStack(输出栈)，直到遇到一个左括号。
        */
        console.log()
        console.log(cur.subString, '是右括号')
        console.log('运算符栈中运算符依次移入输出栈，直到遇到一个左括号')
        console.log()
        var po = operatorStack.pop()
        while (po.subString !== '(' && operatorStack.length > 0) {
          outputStack.push(po)
          po = operatorStack.pop()
        }

        if (po.subString !== '(') {
          throw new Error('error: unmatched ()')
        }
      } else {
        /* 
          operatorStack(操作符栈) 中 运算符 依次移入 outputStack(输出栈)，直到遇到一个优先级小于 cur 的运算符 或是 左括号。
        */
        console.log()
        console.log(cur.subString, '是右括号以外的运算符')
        console.log('运算符栈中运算符依次移入输出栈，直到遇到一个优先级小于 cur 的运算符 或是 左括号')
        console.log()
        while (
          operatorStack.length > 0 &&
          prioraty(operatorStack[operatorStack.length - 1].subString, cur.subString) &&
          operatorStack[operatorStack.length - 1].subString !== '('
        ) {
          outputStack.push(operatorStack.pop())
        }

        operatorStack.push(cur)
      }
    } else {
      console.log()
      console.log(cur.subString, '不是运算符直接进输出栈')
      console.log()
      // 非运算符直接入输出栈
      outputStack.push(cur)
    }
    show2()
  }

  // 处理操作符栈中的剩余操作符，全部入输出栈
  if (operatorStack.length > 0) {
    console.log('-----', parseResult.map(d => '-').join(''), '-----')
    console.log('处理操作符栈中的剩余操作符，全部入输出栈')
    console.log()
    while (operatorStack.length > 0) {
      if (
        operatorStack[operatorStack.length - 1].subString === ')' ||
        operatorStack[operatorStack.length - 1].subString === '('
      ) {
        // 此时操作符栈 不应存在 ( 或 )
        throw new Error('error: unmatched ()')
      }
      outputStack.push(operatorStack.pop())
    }
    show2()
  }
  return outputStack
}

let exp = '10+2*(3+4)/15'
let rnps = dal2Rpn(parseFormulaStr(exp))
